home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackTree.h < prev    next >
Encoding:
Text File  |  1997-06-28  |  1.1 KB  |  51 lines  |  [TEXT/CWIE]
  1. // RedBlackTree.h
  2.  
  3. #ifndef RedBlackTree_h
  4. #define RedBlackTree_h
  5.  
  6. #ifndef Tree_h
  7. #include "Tree.h"
  8. #endif
  9. #ifndef Integers_h
  10. #include "Integers.h"
  11. #endif
  12.  
  13. class RedBlackTree: private Tree
  14.   {
  15.     friend class RedBlackNode;
  16.     
  17.     private:
  18.         uint32 blackHeight;
  19.         
  20.         static RedBlackNode *DownCast( TreeNode *n );
  21.         static const RedBlackNode *DownCast( const TreeNode *n );
  22.         
  23.         void FixRedChain( RedBlackNode& );
  24.         void Redden( RedBlackNode& );
  25.         
  26.     public:
  27.         RedBlackTree();
  28.         ~RedBlackTree();
  29.         
  30.         void Add( RedBlackNode&, AtRoot );
  31.         void Add( RedBlackNode&, Before, RedBlackNode& );
  32.         void Add( RedBlackNode&, After, RedBlackNode& );
  33.         
  34.         void Remove( RedBlackNode& );
  35.         void RemoveAll();
  36.         
  37.         Tree::IsEmpty;
  38.         
  39.         const RedBlackNode *Root() const        { return DownCast( Tree::Root() ); }
  40.         const RedBlackNode *First() const    { return DownCast( Tree::First() ); }
  41.         const RedBlackNode *Last() const        { return DownCast( Tree::Last() ); }
  42.         
  43.         RedBlackNode *Root()                        { return DownCast( Tree::Root() ); }
  44.         RedBlackNode *First()                    { return DownCast( Tree::First() ); }
  45.         RedBlackNode *Last()                        { return DownCast( Tree::Last() ); }
  46.         
  47.         bool Valid() const;
  48.   };
  49.  
  50. #endif
  51.